
public class HeapSort {

    public static final int NUM_ITEMS = 10;

    public static int nums[] = new int[NUM_ITEMS];
    

    public static void main(String[] args) {   

        for(int i = 0; i < NUM_ITEMS; i++) nums[i] = i;

        System.out.println("Successive heap array after exchange " + "with root-item:");

        HeapSort(NUM_ITEMS);

    }

    

    public static void AddToHeap(int itemNum, int numItems) {

        int leftChild = 2*itemNum+1;

        if (leftChild > numItems-1) return; //if nums[i] has no children

        else{ int rightChild = 2*itemNum+2, largestChild;

              if (rightChild > numItems -1 || nums[rightChild] < nums[leftChild]) 
            	  largestChild = leftChild;

              else largestChild = rightChild;
        
              if (nums[largestChild] > nums[itemNum]){
            	  int temp = nums[largestChild];

                  nums[largestChild] = nums[itemNum];

                  nums[itemNum] = temp;
              }	  
      
          AddToHeap(largestChild, numItems);
        }
    }

    

    public static void MakeHeap(int numItems) {

        if (1 == numItems) return; 

        for(int i = numItems/2-1; i > -1; i--) {

            AddToHeap(i, numItems); }

    }

    

    public static void HeapSort(int numItems) {

        if (1 == numItems) return;
        
        else{ 
                if (numItems == NUM_ITEMS) { //if top level call
     
                   MakeHeap(numItems); }
        
                System.out.print("["+nums[0]);

                for (int i = 1; i < numItems; i++) 
                   System.out.print(", "+nums[i]);

                System.out.println("]");

                int temp = nums[0];

                nums[0] = nums[numItems-1];

                nums[numItems-1] = temp;

                AddToHeap(0, numItems-1); 
                      
                System.out.print("["+nums[0]);

                for (int i = 1; i < numItems; i++) 
                    System.out.print(", "+nums[i]);

                System.out.println("]");

                HeapSort(numItems-1);
                
        }

    }

}